The present invention relates to the field of data processing, and more particularly relates to a pattern matching accelerator (PMA) and related sub-systems for use in high-speed pattern matching applications.
Current PMA systems utilize deterministic finite automaton (DFA) for high-speed patent matching. A DFA is a finite state machine that accepts or rejects finite strings of symbols and produces a unique computation or run of the automaton for each input string. A DFA may be illustrated as a state diagram but can be implemented in hardware or software. DFAs recognize a set of regular languages, which are formal languages that can be expressed using regular expressions.
In systems configured to perform massive regular expression matching at high speed, scaling problems may be observed that prevent known DFA processing techniques and functions from working efficiently. For example, regular expression scanners involving a few thousand patterns for virus or intrusion detection can be dramatically slowed as a growing number of new virus and intrusion patterns are added. As the size of the DFA grows, the memory required for storing state transitions in the DFA also increases. In many cases, the memory required for storing the state transitions span multiple memory structures, which can increase the time required to access various state transitions.